package com.future;

import com.future.util.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: 654. 最大二叉树
 * <p>
 * 输入：nums = [3,2,1,6,0,5]
 * 输出：[6,3,5,null,2,0,null,null,1]
 *
 * @author weiruibai.vendor
 * Date: 2022/12/29 09:25
 */
public class Solution_654 {

    private static Solution_654 instance = new Solution_654();

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 1, 6, 0, 5};
        TreeNode node = instance.constructMaximumBinaryTree(nums);
        System.out.println(node);
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Map<Integer, Integer> mapIndex = new HashMap<>();
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            mapIndex.put(nums[i], i);
        }
        TreeNode head = new TreeNode(max);
        head.left = buildTree(mapIndex, nums, 0, mapIndex.get(max) - 1);
        head.right = buildTree(mapIndex, nums, mapIndex.get(max) + 1, nums.length-1);
        return head;
    }

    private TreeNode buildTree(Map<Integer, Integer> mapIndex, int[] nums, int start, Integer end) {
        if (start > end) {
            return null;
        }
        int max = nums[start];
        for (int i = start; i <= end; i++) {
            max = Math.max(max, nums[i]);
        }
        TreeNode root = new TreeNode(max);
        root.left = buildTree(mapIndex, nums, start, mapIndex.get(max) - 1);
        root.right = buildTree(mapIndex, nums, mapIndex.get(max) + 1, end);
        return root;
    }
}
